package sword.chapter4LinkList;

import leetcode.t4LinkedList.ListNode;

import java.util.ArrayList;

/**
 * 重排链表
 * <p>
 * 1. 快慢指针 起点在dummy 0（负1节点）。保证第一次循环，慢指针在1节点、快指针在3节点，快指针在尾结点时，慢指针在中间位置
 * 2. 链接时，三指针移动。（指针指向某一节点，节点上都是有值保存）
 * 指针3（p3）prev记录上一节点位置（默认0）
 * temp记录p1的下一位置，用于后面重新给p1赋值前进一步
 * 指针3（p3）prev连续两次赋值 第一次赋值p1,第二次赋值p2
 * 指针3（p3）prev指向最新位置p2
 * p1前进一步（指向temp）p2前进一步
 * <p>
 * 总结：
 * 三指针移动，第三个指针赋值两次，并将指针指向最新节点
 * 快慢指针要注意起点位置，根据具体场景决定
 * 1 2 3 4 5 6
 * 1 6 2 5 3 4
 *
 * @author K
 */
public class S26ReorderList {
    public static void main(String[] args) {
        ListNode nodeA = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        nodeA.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        ListNode listNode = s26(nodeA);
//        s26A(nodeA);
//        reorderList(nodeA);
        System.out.println();
    }

    public static void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        int len = 0;
        ListNode h = head;
        //求出节点数
        while (h != null) {
            len++;
            h = h.next;
        }

        reorderListHelper(head, len);
    }

    private static ListNode reorderListHelper(ListNode head, int len) {
        if (len == 1) {
            ListNode outTail = head.next;
            head.next = null;
            return outTail;
        }
        if (len == 2) {
            ListNode outTail = head.next.next;
            head.next.next = null;
            return outTail;
        }
        //得到对应的尾节点，并且将头结点和尾节点之间的链表通过递归处理
        ListNode tail = reorderListHelper(head.next, len - 2);
        ListNode subHead = head.next;//中间链表的头结点
        head.next = tail;
        ListNode outTail = tail.next;  //上一层 head 对应的 tail
        tail.next = subHead;
        return outTail;
    }


    public static ListNode s26(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy.next;
        ListNode fast = slow.next;
        while (slow != null && fast != null) {
            if (fast.next == null) {
                break;
            }
            slow = slow.next;
            fast = fast.next;
            if (fast.next != null) {
                fast = fast.next;
            }
        }


        ListNode temp = slow.next;
        slow.next = null;
//        link(head, reverseList(temp), dummy);
        link2(head, reverseList(temp));
        return dummy;
    }

    /**
     * @param node1 前半截
     * @param node2 后半截
     * @param head  0+前半截
     */
    private static void link(ListNode node1, ListNode node2, ListNode head) {
        ListNode prev = head;
        while (node1 != null && node2 != null) {
            ListNode temp = node1.next;

            prev.next = node1;
//            node1.next = node2;
            prev.next.next = node2;
            prev = node2;  // 上一节点移动到最新节点node2

            node1 = temp;
            node2 = node2.next;
        }

        if (node1 != null) {
            prev.next = node1;
        }
    }

    public static ListNode link2(ListNode headA, ListNode headB) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        while (headA != null && headB != null) {
            ListNode temp = headA.next;
            prev.next = headA;
            prev.next.next = headB;
            prev = headB;

            headA = temp;
            headB = headB.next;
        }
        if (headA != null) {
            prev.next = headA;
        }
        return dummy.next;
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void s26A(ListNode head) {
        if (head == null) {
            return;
        }
        ArrayList<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }

        int i = 0, j=list.size()-1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            //偶数个节点的情况，会提前相遇
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
    }
}
